//
// Created by 麻再挺 on 2021/12/22.
//

#include "quick_sort.h"

void quick_sort(int arr[], int start, int end) {
    // 赋值起始位置
    int i = start, j = end;
    // 设置基准值
    int tmp = arr[start];
    while (i < j) {
        // 位置左移
        while (i < j && tmp < arr[j]) j--;
        // 位置右移
        if (i < j) {
            // 将arr[j]放到arr[i]的位置上
            arr[i] = arr[j];
            i++;
        }
        // 位置右移
        while (i < j && arr[i] <= tmp) i++;
        if (i < j) {
            // 将大于基准值的s[j]放到s[i]位置
            arr[j] = arr[i];
            // 位置左移
            j--;
        }
    }
    // 将基准值放在中间
    arr[i] = tmp;
    if (start < i) {
        quick_sort(arr, start, j - 1);
    }
    if (i < end) {
        quick_sort(arr, j + 1, end);
    }
}